package com.hspedu.set_;

import java.util.HashSet;

/**
 * @Author Stringzhua
 * @Date 2024/3/11 21:28
 * description:HashSet的添加元素底层如何实现?
 * hash()+equals()
 */
@SuppressWarnings("all")
public class HashSetSource {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("java");
        hashSet.add("php");
        hashSet.add("java");
        System.out.println("set = " + hashSet);


        /*
        * 对HashSet源码解读:
        * 1.执行HashSet()构造器
        *   public HashSet() {
            map = new HashMap<>();
            }
        * 2.执行add(E e)
        * public boolean add(E e) {//e="java
            return map.put(e, PRESENT)==null; //PRESENT 占位符 [private static final Object PRESENT = new Object();]
            }
        * 3.执行put() 该方法会执行hash(key) 得到hash(key)对应的hash值[这里的哈希值不是HashCode] 算法 h = key.hashCode() ^ (h >>> 16)
        * public V put(K key, V value) {//key="java" value=PRESENT 共享
            return putVal(hash(key), key, value, false, true);
            }
        * 4.执行 putVal
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;  //定义了辅助变量
            //table 就是HashMap的一个数组,类型是Node[]
            //if 语句表示如果当前table 是null,或者大小=0
            //就是第一次扩容,到16个空间.
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //(1)根据key,得到hash去计算该key应该存放table表的哪个索引位置,
            //并且把该位置的对象,赋给p
            //(2)判断p是否为null
            //(2.1)如果p为null,表示还没有存放元素,就创建一个Node (key="java" value=PRESENT)
            //(2.2)就放在该位置 tab[i] = newNode(hash, key, value, null);
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
            //一个开发技巧提示:在需要局部变量(辅助变量)时候,再创建
                Node<K,V> e; K k;//
                // 如果当前位置索引链表的第一个元素,和准备添加的key的哈希值一样,将当前的hash值交给p.hash
                // 并且满足下面两个条件之一:
                // (1)准备加入的 key 和 p 指向的Node 结点的key 是同一个对象
                // (2)p 指向的Node 结点的key 的equals() 和准备加入的key 比较后相同
                // 就不能加入
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //再判断p是不是一棵红黑树
                //如果是一颗红黑树,就调用putTreeVal方法,来进行添加
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {//如果table对应索引位置,已经是一个链表,就使用for循环比较
                    //(1)依次和该链表的每一个元素比较后,都不相同,则加入到该链表的最后
                    //TREEIFY_THRESHOLD=8,注意在把元素添加到链表后,立即判断 该链表是否已经达到八个结点
                    // 如果达到就调用treeifyBin(tab, hash); 对当前链表进行树化(转成红黑树)
                    //注意,在转成红黑树时,还进行一个判断,
                    //判断条件如下:如果该table表的大小<64 [static final int MIN_TREEIFY_CAPACITY = 64;]
                     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                        resize();
                    //(2)在依次比较的过程中,如果有相同的情况,就直接break;
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {//情况(1)
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&//情况(2)
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            //size 就是我们每加入一个结点Node(k,v,h,next),size++
            if (++size > threshold)
                resize();//扩容
            afterNodeInsertion(evict);
            return null;
    }
        * */
    }
}
